package backTrack;

import java.util.ArrayList;
import java.util.List;

public class partition {
    List<List<String>> list = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backTrack(s, 0, 0, new ArrayList<String>());

        return list;
    }

    public void backTrack(String s, int start, int end, List<String> subList) {
        //还有就是没有想清楚end是开还是闭
        if (end == s.length()-1) {
            // 结束了
            subList.add(s.substring(start, end+1));
            if (check(subList)) {
                list.add(new ArrayList<>(subList));
            }
            //一开始忘记remove了
            subList.remove(subList.size()-1);
            return;
        }
        // 选or不选
        
        backTrack(s, start, end + 1, subList);
        subList.add(s.substring(start, end+1));
        backTrack(s, end + 1, end + 1, subList);
        subList.remove(subList.size() - 1);

    }

    public boolean check(List<String> subList) {
        boolean flag = true;
        for (String s : subList) {
            int length = s.length();
            if (length==1) {
                continue;
            }
            for (int i = 0; i <= length / 2; i++) {
                if (s.charAt(i) != s.charAt(length - i - 1)) {
                    return false;
                }
            }
        }

        return flag;
    }

    public static void main(String[] args) {
        partition obj = new partition();
        // String s = "aab";
        String s = "aba";
        List<List<String>> lists = obj.partition(s);
        for (List<String> list : lists) {
            for (String i : list) {
                System.out.println(i);
            }
            System.out.println("============");
        }
        System.out.println("end");
    }
}
